package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC743 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int networkDelayTime(int[][] times, int N, int K) {
            List<int[]>[] edges = new List[N + 1];
            for (int[] time : times) {
                if (null == edges[time[0]]) edges[time[0]] = new ArrayList<>();
                List<int[]> edge = edges[time[0]];
                edge.add(new int[]{time[1], time[2]});
            }

            Queue<Integer> queue = new LinkedList<>();
            Map<Integer, Integer> pathLengthMap = new LinkedHashMap<>();//paths length that end with id :n
            pathLengthMap.put(K, 0);//记录到达节点k的最早时间
            queue.offer(K);
            int curNodeId;

            while (!queue.isEmpty()) {
                curNodeId = queue.poll();
                List<int[]> curEdge = edges[curNodeId];
                if (null == curEdge) continue;

                for (int[] next : curEdge) {
                    int nextId = next[0], nextCost = next[1] + pathLengthMap.get(curNodeId);
                    if (pathLengthMap.containsKey(nextId) && pathLengthMap.get(nextId) <= nextCost) continue;
                    queue.offer(nextId);
                    //update cost.
                    pathLengthMap.put(nextId, nextCost);
                }
            }

            if (pathLengthMap.size() < N) return -1;
            int maxDelayTime = 0;
            for (Integer cost : pathLengthMap.values()) {
                maxDelayTime = Math.max(maxDelayTime, cost);
            }

            return maxDelayTime;
        }
    }

    class Solution_Standard_Answer {
        public int networkDelayTime(int[][] times, int N, int K) {
            Map<Integer, List<int[]>> graph = new HashMap();
            for (int[] edge : times) {
                if (!graph.containsKey(edge[0])) graph.put(edge[0], new ArrayList<int[]>());
                graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
            }

            PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
                    (info1, info2) -> info1[0] - info2[0]);
            heap.offer(new int[]{0, K});

            Map<Integer, Integer> dist = new HashMap();

            while (!heap.isEmpty()) {
                int[] info = heap.poll();
                int curReachDistance = info[0], node = info[1];
                if (dist.containsKey(node)) continue;

                dist.put(node, curReachDistance);
                if (graph.containsKey(node))
                    for (int[] edge : graph.get(node)) {
                        int nei = edge[0], d2 = edge[1];
                        if (!dist.containsKey(nei)) heap.offer(new int[]{curReachDistance + d2, nei});
                    }
            }

            if (dist.size() != N) return -1;
            int ans = 0;
            for (int cand : dist.values())
                ans = Math.max(ans, cand);
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
        //Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
//Output: 2
        int[][] times = InputUtil.toDoubleIntegerArray("[[2,10,98],[43,19,85],[32,11,35],[40,39,93],[21,27,51],[16,36,4],[9,21,25],[37,12,86],[37,5,65],[45,6,56],[6,7,65],[4,2,85],[41,35,95],[29,24,85],[24,46,62],[28,11,49],[32,22,19],[10,8,33],[48,47,87],[14,41,42],[22,47,51],[39,2,52],[24,43,38],[21,23,61],[7,46,57],[18,20,56],[18,49,23],[15,45,62],[30,35,57],[3,31,60],[15,16,28],[3,39,50],[14,45,95],[23,17,20],[43,36,76],[33,28,45],[31,4,9],[25,18,91],[12,27,93],[44,37,86],[28,1,1],[6,5,39],[8,21,85],[6,43,53],[26,35,40],[4,18,18],[49,50,71],[10,27,90],[1,38,67],[45,33,3],[31,11,56],[34,18,62],[33,13,30],[26,17,57],[12,7,60],[31,27,60],[31,50,69],[7,41,70],[46,8,64],[28,13,96],[40,21,29],[8,34,54],[35,16,17],[17,43,33],[24,5,41],[36,37,68],[46,17,69],[15,25,9],[35,22,68],[1,2,83],[47,41,53],[29,50,38],[33,36,56],[49,37,76],[5,29,61],[42,49,6],[10,20,21],[37,30,57],[8,50,58],[9,33,6],[2,39,84],[1,27,69],[39,33,70],[40,34,57],[17,40,37],[28,33,37],[37,43,6],[8,31,37],[15,40,37],[25,1,71],[34,2,59],[20,4,38],[39,42,20],[12,34,55],[21,50,45],[8,29,77],[47,15,71],[3,24,51],[44,30,14],[44,3,99],[45,13,69],[48,3,7],[42,23,20],[25,31,90],[48,4,4],[44,21,28],[49,44,31],[41,34,74],[22,1,67],[24,50,63],[38,21,61],[40,31,54],[15,1,28],[45,42,53],[22,39,8],[28,35,28],[6,35,24],[38,25,59],[14,48,9],[32,21,11],[47,9,33],[10,50,63],[15,44,57],[6,49,80],[9,32,37],[14,5,41],[24,19,38],[35,2,9],[46,48,69],[30,8,68],[43,21,34],[9,17,43],[14,15,24],[12,24,84],[43,12,99],[9,25,54],[2,48,22],[26,2,79],[23,21,10],[32,41,5],[5,27,13],[9,31,32],[22,30,92],[48,34,94],[48,8,34],[32,33,35],[11,8,57],[24,39,99],[29,43,76],[44,13,96],[23,50,92],[15,10,24],[48,31,3],[40,28,89],[36,25,48],[20,8,31],[7,21,90],[16,44,28],[16,24,73],[44,19,37],[42,44,88],[36,8,97],[10,5,77],[13,47,7],[4,32,33],[3,4,91],[36,12,11],[26,30,56],[6,45,31],[31,40,49],[19,31,92],[7,16,50],[7,25,6],[36,39,54],[39,29,96],[44,22,31],[5,35,56],[34,41,13],[30,22,44],[16,23,17],[18,29,43],[24,15,32],[31,9,76],[19,37,24],[12,8,55],[18,42,63],[4,34,28],[35,7,72],[6,30,36],[8,45,61],[26,14,39],[4,3,16],[13,31,86],[1,5,97],[9,12,17],[2,27,20],[36,6,4],[42,28,11],[21,17,69],[17,28,96],[30,19,66],[19,23,69],[2,24,36],[9,23,46],[22,40,50],[49,12,85],[4,17,28],[2,1,48],[20,30,44],[2,49,11],[20,23,32],[8,9,83],[31,47,93],[6,46,65],[47,46,65],[19,25,62],[14,4,2],[36,35,46],[37,33,9],[42,15,16],[28,48,13],[21,3,60],[38,49,57],[3,7,39],[23,33,53],[26,39,67],[31,41,4],[15,39,40],[50,49,97],[6,42,61],[23,19,58],[38,42,62],[50,29,61],[7,34,69],[48,6,4],[1,31,92],[20,11,82],[24,28,22],[14,29,72],[11,34,64],[23,8,84],[33,45,75],[46,44,6],[9,2,89],[28,49,94],[32,2,27],[24,21,39],[17,33,59],[45,5,70],[31,21,94],[38,6,28],[35,33,73],[30,41,31],[32,30,11],[32,27,42],[33,4,18],[4,43,75],[50,12,7],[9,8,64],[35,25,77],[42,4,13],[27,29,42],[17,11,75],[49,22,57],[25,16,89],[30,34,94],[24,12,45],[37,19,4],[47,33,84],[36,20,11],[39,45,20],[46,6,77],[5,32,95],[47,11,78],[41,36,89],[37,23,60],[45,29,53],[14,40,18],[27,6,95],[17,3,67],[22,9,15],[29,39,19],[10,34,65],[22,14,58],[8,4,96],[30,14,38],[50,10,16],[5,24,58],[23,2,65],[21,18,67],[29,3,69],[17,25,81],[2,40,52],[15,50,59],[20,46,90],[35,34,39],[45,3,46],[19,21,75],[41,38,95],[24,35,0],[42,9,81],[43,1,85],[9,50,45],[29,46,87],[30,9,32],[26,28,94],[46,50,22],[37,38,69],[19,20,92],[3,20,33],[12,3,77],[14,39,35],[13,36,65],[8,23,80],[41,4,38],[23,29,18],[20,25,17],[7,13,30],[27,7,82],[48,42,45],[3,19,58],[43,6,23],[28,22,80],[21,6,41],[46,36,11],[17,10,29],[10,22,85],[24,4,63],[30,39,63],[21,34,65],[41,45,7],[46,18,86],[19,50,89],[22,23,96],[16,18,32],[27,36,43],[6,47,17],[44,20,20],[9,1,58],[45,37,12],[39,46,9],[31,7,73],[2,29,69],[19,48,1],[46,33,97],[3,29,14],[48,44,79],[19,34,27],[14,46,84],[48,26,42],[22,42,49],[19,46,44],[49,32,6],[47,32,92],[5,31,37],[36,3,76],[4,36,55],[20,33,91],[17,8,34],[41,39,7],[32,38,27],[29,34,30],[23,32,12],[31,30,93],[24,34,23],[11,20,75],[40,25,13],[45,44,45],[6,23,51],[46,30,35],[33,7,13],[16,40,36],[49,2,16],[29,47,41],[14,22,52],[35,50,43],[10,15,37],[5,10,75],[48,18,61],[44,38,18],[11,27,54],[10,30,22],[40,26,64],[3,49,68],[40,48,11],[49,3,73],[27,21,39],[4,5,42],[49,42,60],[10,18,14],[21,49,89],[10,26,53],[14,24,21],[35,3,36],[33,8,61],[11,28,53],[37,18,6],[41,11,4],[16,1,85],[36,49,26],[45,26,79],[11,49,52],[13,24,36],[18,11,20],[25,24,81],[4,27,17],[22,33,59],[32,40,40],[2,5,42],[39,41,92],[15,37,67],[46,47,65],[48,12,91],[36,29,53],[7,5,76],[40,8,53],[9,29,87],[18,10,26],[10,12,83],[26,44,16],[12,13,61],[11,30,11],[47,2,73],[5,8,50],[44,15,55],[2,44,42],[21,5,21],[30,18,56],[31,20,31],[26,36,44],[7,18,9],[30,38,58],[33,14,12],[40,16,6],[5,21,59],[50,15,80],[4,38,11],[22,44,92],[41,27,69],[8,28,79],[27,40,59],[16,48,91],[29,10,83],[44,18,87],[16,30,88],[31,12,91],[18,23,14],[5,40,86],[34,13,93],[12,43,71],[1,4,36],[50,47,67],[9,30,60],[29,19,76],[8,7,8],[19,1,77],[43,15,40],[8,22,32],[46,5,44],[39,18,88],[12,20,91],[48,19,38],[17,30,67],[28,10,88],[6,17,44],[16,37,96],[43,29,11],[34,38,32],[16,33,36],[12,23,56],[1,34,75],[44,34,46],[32,50,75],[35,42,85],[3,36,50],[41,33,93],[29,9,77],[46,41,65],[9,16,21],[11,1,97],[5,34,95],[38,36,70],[41,14,6],[4,47,70],[49,27,28],[26,24,21],[37,15,42],[37,14,48],[21,9,36],[37,9,71],[47,28,25],[49,31,23],[19,29,50],[5,12,50],[43,25,98],[15,35,86],[22,15,63],[45,1,73],[1,43,98],[33,17,17],[13,19,64],[20,42,84],[17,50,90],[31,2,32],[7,2,97],[42,39,20],[6,2,64],[9,27,32],[27,8,10],[45,27,22],[13,41,93],[7,27,59],[8,17,39],[49,10,99],[21,47,0],[16,5,49],[25,17,93],[1,41,8],[43,34,64],[19,44,21],[37,35,81],[24,41,58],[21,43,46],[27,22,67],[44,28,16],[18,45,61],[18,35,69],[10,21,85],[30,16,6],[16,50,39],[31,43,59],[23,3,29],[17,49,58],[38,18,1],[22,10,97],[32,31,62],[48,33,2],[4,19,84],[46,28,58],[25,50,17],[13,18,70],[30,5,41],[39,4,32],[36,23,84],[4,29,15],[15,18,94],[18,36,30],[15,14,88],[35,14,56],[39,8,46],[34,17,75],[37,47,42],[21,39,57],[38,34,76],[26,16,93],[39,5,8],[13,20,75],[4,49,9],[19,7,50],[26,3,46],[17,36,12],[44,25,60],[37,45,48],[46,34,83],[24,9,49],[4,28,10],[25,5,15],[25,15,34],[31,17,11],[35,13,28],[22,27,71],[46,37,9],[42,37,56],[26,21,80],[49,35,74],[28,45,0],[25,49,96],[5,17,7],[38,12,56],[45,21,98],[31,28,25],[3,10,61],[46,20,53],[2,26,85],[12,16,15],[1,28,71],[12,37,17],[35,37,49],[14,13,52],[23,24,73],[22,21,61],[19,40,67],[19,16,45],[32,34,60],[34,44,98],[41,47,54],[15,22,27],[1,19,5],[23,12,70],[43,27,16],[27,12,76],[9,24,12],[4,22,64],[34,9,66],[26,7,20],[41,29,0],[41,22,0],[22,19,50],[33,40,95],[34,30,48],[48,35,71],[30,29,95],[38,19,1],[28,40,53],[36,19,27],[10,46,15],[37,48,37],[18,46,35],[3,17,49],[22,49,77],[29,6,54],[21,16,12],[27,37,23],[24,2,98],[28,39,95],[17,6,40],[4,10,8],[3,32,56],[33,2,44],[13,8,50],[14,12,95],[42,50,70],[15,2,68],[44,40,63],[11,47,55],[14,7,64],[21,1,40],[18,13,49],[18,9,43],[14,42,56],[30,28,58],[21,44,18],[32,26,12],[50,17,85],[50,9,2],[15,9,69],[25,2,85],[15,5,57],[43,14,22],[23,44,80],[43,37,98],[12,35,81],[39,50,81],[5,37,32],[16,39,98],[24,10,73],[27,47,39],[36,11,95],[28,5,49],[22,41,99],[36,27,32],[16,31,63],[49,46,51],[47,21,13],[12,11,85],[23,9,80],[30,20,49],[7,24,98],[42,33,92],[20,48,72],[33,48,69],[42,2,67],[40,13,80],[25,37,88],[8,16,57],[6,48,8],[12,41,37],[47,40,6],[35,36,47],[38,14,86],[28,23,53],[37,29,29],[19,38,34],[18,47,55],[8,39,21],[22,29,58],[18,21,17],[2,8,64],[39,13,5],[38,2,68],[26,29,42],[30,17,20],[9,35,10],[45,2,56],[2,12,44],[26,34,51],[46,1,52],[3,15,92],[18,22,29],[21,42,5],[50,34,86],[47,3,14],[41,6,22],[19,17,2],[44,50,53],[41,50,57],[46,16,49],[13,38,79],[35,29,36],[36,13,74],[13,9,5],[24,36,70],[23,40,60],[24,49,55],[42,1,19],[31,32,6],[11,18,41],[25,42,94],[45,14,1],[29,26,14],[48,14,56],[31,24,47],[7,23,55],[50,23,26],[30,4,32],[16,19,60],[29,21,91],[6,37,27],[43,48,17],[30,31,41],[28,37,15],[38,9,66],[43,44,7],[17,18,25],[10,28,68],[48,7,7],[8,49,28],[8,24,6],[40,11,95],[1,29,89],[6,13,13],[2,50,63],[29,18,60],[35,27,41],[36,34,91],[17,21,34],[41,16,7],[36,18,35],[27,13,75],[39,20,27],[42,21,90],[20,38,51],[6,16,44],[44,2,87],[22,37,19],[14,2,78],[1,21,66],[27,33,41],[32,29,38],[23,49,28],[32,49,4],[28,42,55],[1,45,78],[1,16,96],[11,19,15],[49,43,13],[29,36,2],[13,35,7],[13,7,82],[44,46,73],[46,49,67],[27,1,34],[23,30,34],[11,17,96],[31,33,96],[24,48,24],[39,47,57],[31,25,19],[39,9,15],[11,32,52],[38,10,63],[24,22,29],[22,4,11],[10,44,89],[12,33,35],[19,15,61],[38,3,21],[5,38,54],[16,22,59],[4,6,98],[50,45,39],[5,7,33],[5,28,97],[45,34,12],[16,43,67],[40,10,6],[3,21,24],[27,28,82],[27,15,70],[35,8,24],[19,47,68],[36,42,35],[6,34,17],[46,2,85],[42,40,83],[18,17,62],[28,29,42],[48,13,49],[25,26,5],[45,25,73],[31,18,60],[4,16,22],[17,7,11],[50,27,27],[6,41,6],[50,41,69],[49,17,96],[4,13,20],[38,39,82],[41,19,17],[40,12,92],[3,13,18],[47,38,66],[3,37,8],[25,19,91],[37,41,71],[10,16,20],[29,33,15],[28,6,75],[40,24,5],[16,20,94],[34,25,32],[42,46,68],[18,16,11],[33,37,36],[36,22,87],[44,8,40],[15,21,31],[10,42,0],[28,3,55],[36,38,42],[22,32,45],[34,1,42],[38,30,93],[1,47,61],[43,11,83],[26,22,74],[26,1,29],[31,36,18],[25,7,49],[21,36,56],[4,39,50],[47,42,40],[29,37,46],[2,37,44],[7,48,55],[30,25,80],[31,6,60],[25,8,9],[31,13,49],[33,11,90],[23,39,76],[21,40,64],[17,4,94],[2,3,75],[32,35,30],[39,38,11],[1,37,43],[41,23,57],[45,19,29],[46,21,83],[23,4,67],[3,48,21],[47,39,16],[34,50,66],[23,45,79],[2,15,30],[9,6,70],[15,4,91],[28,34,28],[47,7,14],[35,26,99],[36,44,73],[33,23,74],[47,5,35],[20,14,91],[35,41,26],[31,29,54],[13,17,11],[38,16,98],[16,28,10],[38,23,94],[2,36,44],[38,27,22],[20,7,76],[46,29,3],[45,12,94],[12,4,28],[21,10,52],[42,16,80],[12,49,71],[2,4,89],[13,48,16],[20,12,77],[6,27,65],[2,19,58],[33,41,67],[34,16,45],[34,37,45],[29,40,49],[19,4,98],[10,4,46],[26,4,98],[50,6,69],[8,40,59],[28,24,93],[13,39,38],[46,27,84],[24,18,85],[34,28,56],[3,34,44],[28,38,42],[30,45,11],[39,34,23],[16,9,16],[28,50,55],[44,16,59],[27,41,0],[45,35,73],[41,17,97],[5,45,93],[39,22,40],[14,28,89],[20,6,31],[11,16,95],[36,24,20],[11,13,52],[9,28,22],[13,28,65],[19,13,78],[48,5,99],[21,13,98],[37,10,33],[30,15,40],[27,2,97],[33,26,59],[11,43,27],[25,27,22],[44,42,12],[30,1,97],[41,31,28],[24,25,46],[47,4,48],[24,3,49],[18,33,24],[41,7,2],[14,36,16],[29,31,79],[11,9,36],[13,30,80],[18,28,25],[6,3,77],[5,22,61],[50,38,83],[33,27,63],[25,23,95],[9,7,60],[28,19,13],[35,23,43],[42,45,4],[36,32,56],[41,1,82],[3,8,6],[17,34,15],[4,31,70],[48,37,43],[6,12,0],[43,45,8],[17,12,48],[17,44,2],[38,41,8],[25,20,61],[7,42,60],[18,6,36],[10,1,44],[26,12,92],[44,7,94],[26,50,78],[35,19,53],[10,49,91],[5,36,8],[10,24,17],[10,19,94],[23,13,87],[31,10,55],[40,37,54],[50,31,54],[29,35,52],[23,42,18],[37,31,51],[48,36,40],[13,11,41],[43,17,78],[41,26,21],[16,42,71],[6,26,16],[40,18,28],[2,11,71],[18,39,13],[43,13,35],[17,23,41],[27,46,1],[16,21,9],[18,2,71],[13,4,62],[20,17,27],[20,37,49],[36,10,43],[45,30,76],[16,4,83],[33,5,6],[23,25,20],[43,2,91],[11,50,28],[46,11,71],[10,17,16],[22,12,9],[26,47,43],[32,6,15],[7,26,95],[46,25,65],[7,3,54],[19,2,83],[16,14,6],[25,30,74],[17,24,96],[24,27,28],[12,42,57],[36,9,99],[3,50,19],[49,34,94],[24,32,24],[9,5,1],[40,9,86],[48,27,30],[30,48,52],[33,15,88],[27,18,57],[34,45,36],[44,49,89],[33,10,76],[20,31,25],[48,11,10],[34,43,57],[14,27,19],[31,37,83],[45,20,27],[32,15,26],[21,48,85],[47,17,17],[23,15,79],[24,44,35],[1,17,10],[20,10,75],[48,29,58],[42,34,21],[18,7,70],[5,3,86],[3,1,10],[3,25,3],[40,27,21],[40,33,24],[10,35,33],[12,17,22],[15,27,24],[6,20,17],[39,49,63],[46,24,30],[8,46,77],[43,26,18],[33,46,31],[49,18,97],[27,45,39],[9,10,59],[17,29,76],[20,22,55],[31,5,50],[7,49,89],[2,34,88],[43,33,53],[25,45,86],[49,30,68],[5,30,10],[24,40,11],[7,31,88],[9,40,83],[32,4,34],[3,44,87],[1,23,8],[7,4,18],[31,44,81],[39,26,21],[30,26,57],[45,38,23],[35,46,23],[18,1,9],[12,29,11],[14,3,19],[23,7,89],[23,43,26],[44,29,52],[26,5,61],[36,4,89],[40,19,6],[14,32,86],[25,46,89],[46,35,21],[14,23,51],[29,49,85],[49,40,70],[2,31,31],[25,21,49],[31,19,59],[28,8,4],[41,18,50],[17,9,33],[48,40,7],[20,41,91],[7,22,10],[16,49,69],[22,46,74],[27,14,99],[2,17,26],[29,23,96],[38,24,42],[29,16,48],[50,28,65],[12,2,14],[11,3,80],[40,4,31],[43,42,61],[26,38,76],[50,30,4],[6,44,44],[17,32,62],[18,48,25],[22,31,14],[25,12,8],[49,13,33],[11,21,52],[4,20,84],[19,39,33],[46,10,63],[43,9,47],[8,44,48],[4,33,65],[29,30,75],[38,47,87],[8,35,20],[3,47,84],[14,33,8],[31,34,7],[7,35,38],[7,40,21],[22,18,2],[20,24,73],[10,29,34],[48,38,73],[30,24,32],[5,19,91],[41,8,97],[22,48,32],[20,16,68],[47,37,93],[20,45,25],[32,23,59],[39,36,8],[27,9,38],[2,43,94],[22,34,35],[5,14,93],[26,31,13],[8,42,62],[33,25,85],[42,31,90],[43,23,37],[14,9,72],[50,5,49],[16,47,55],[23,41,17],[7,15,2],[1,30,74],[6,21,6],[46,15,31],[33,31,39],[35,48,30],[34,4,80],[46,7,46],[20,49,16],[28,15,70],[29,45,97],[34,15,3],[10,23,15],[43,28,47],[45,9,15],[23,5,73],[17,2,58],[34,7,40],[15,42,57],[26,19,81],[11,31,5],[28,25,83],[28,27,52],[20,40,44],[6,36,12],[19,6,84],[12,14,9],[22,13,1],[50,37,36],[27,16,88],[50,4,60],[39,1,15],[23,20,24],[30,7,88],[45,28,6],[3,12,70],[18,24,52],[15,17,43],[1,6,21],[18,44,23],[22,6,11],[47,16,46],[35,11,75],[40,14,81],[13,16,44],[7,30,12],[1,32,17],[14,47,70],[19,11,93],[42,47,33],[32,25,73],[33,19,60],[48,15,66],[29,28,68],[12,47,44],[13,12,90],[35,31,0],[47,13,12],[11,45,86],[6,22,3],[38,40,63],[32,17,83],[37,28,73],[38,5,48],[11,46,63],[48,30,18],[5,1,21],[11,12,19],[47,29,87],[37,21,35],[36,2,53],[25,35,94],[11,15,42],[28,14,72],[35,9,12],[46,23,35],[35,45,70],[48,45,59],[13,37,39],[35,21,43],[43,3,50],[9,49,72],[4,12,91],[18,12,93],[15,7,4],[27,50,72],[11,35,25],[5,39,75],[49,9,70],[17,27,76],[46,42,62],[18,41,44],[27,49,12],[40,41,73],[16,35,33],[42,11,63],[3,5,56],[2,47,82],[1,11,20],[14,10,16],[19,22,32],[16,29,67],[27,38,65],[45,46,9],[4,48,64],[1,22,16],[30,47,40],[50,20,73],[41,13,45],[29,8,29],[3,27,42],[11,26,86],[34,29,57],[11,25,79],[8,26,62],[5,20,64],[29,15,18],[30,40,22],[8,37,34],[33,16,51],[16,25,26],[28,32,48],[45,15,64],[6,28,94],[2,22,47],[27,43,20],[15,28,52],[7,47,37],[4,23,47],[32,8,35],[20,18,99],[42,12,13],[43,31,13],[2,16,17],[50,16,63],[42,3,5],[13,14,48],[25,29,64],[47,30,56],[10,31,23],[29,38,10],[37,20,76],[44,32,17],[15,13,40],[7,17,46],[21,32,94],[9,34,86],[5,13,94],[6,50,74],[50,33,43],[7,38,24],[37,39,59],[40,43,91],[8,18,70],[3,23,25],[29,14,31],[18,38,75],[12,26,65],[24,29,19],[39,3,7],[4,50,38],[34,32,90],[22,20,88],[41,9,15],[43,5,4],[14,17,74],[2,21,82],[35,17,64],[32,12,53],[5,33,93],[46,43,9],[49,28,42],[47,31,35],[39,23,53],[25,22,16],[32,19,49],[45,24,54],[29,2,48],[21,26,69],[19,8,4],[3,16,71],[10,41,48],[30,49,56],[27,23,62],[5,42,15],[38,32,0],[43,35,80],[48,28,95],[15,48,41],[9,42,54],[3,33,46],[38,45,4],[6,8,71],[2,46,21],[19,14,21],[33,3,19],[12,39,34],[42,38,32],[49,11,80],[28,16,62],[26,15,51],[29,12,5],[38,46,99],[29,25,25],[45,36,38],[13,44,27],[8,43,54],[44,4,22],[41,44,44],[33,49,23],[11,6,65],[17,42,58],[9,41,94],[40,5,75],[40,1,70],[40,49,35],[50,7,25],[4,40,69],[2,33,16],[38,31,74],[35,6,2],[35,44,1],[41,21,46],[1,25,38],[22,26,68],[39,48,53],[21,14,97],[7,1,29],[32,45,53],[16,2,55],[9,43,17],[18,19,13],[2,23,25],[24,37,74],[32,39,4],[15,29,35],[9,47,46],[37,11,85],[9,14,58],[19,35,66],[4,45,98],[14,35,14],[2,45,51],[10,48,97],[8,10,17],[8,38,54],[31,1,30],[42,5,52],[26,6,59],[23,16,47],[48,2,39],[39,21,68],[41,24,42],[40,3,19],[47,12,43],[12,9,22],[20,44,72],[46,45,31],[5,2,87],[27,3,54],[35,28,20],[18,27,7],[27,32,54],[4,21,96],[31,23,50],[26,43,43],[46,26,38],[30,50,36],[26,32,61],[14,1,72],[49,33,11],[20,28,19],[47,18,96],[6,39,1],[31,3,41],[33,18,89],[7,6,57],[21,38,63],[42,17,82],[38,35,31],[42,43,12],[8,1,12],[39,6,83],[25,39,90],[17,26,19],[9,3,31],[18,3,95],[7,10,30],[35,12,89],[3,22,71],[13,15,31],[36,48,92],[1,50,27],[17,39,23],[30,43,9],[15,33,65],[32,24,7],[22,50,23],[3,41,26],[41,5,35],[26,8,84],[1,24,29],[25,9,53],[34,33,52],[34,26,99],[2,35,14],[45,39,49],[27,44,4],[27,17,85],[25,13,55],[17,15,46],[16,8,35],[50,14,83],[46,13,4],[14,50,47],[12,46,25],[42,32,29],[50,19,0],[14,31,20],[4,42,15],[48,39,13],[45,40,89],[10,11,66],[38,4,87],[12,5,42],[35,40,39],[44,17,69],[20,29,6],[48,24,42],[19,27,58],[41,2,73],[15,3,74],[22,38,31],[17,20,52],[34,23,7],[9,39,59],[6,33,22],[28,20,54],[34,31,0],[42,19,13],[10,14,39],[6,24,44],[12,31,92],[40,20,67],[9,36,66],[21,35,8],[25,40,88],[17,13,57],[16,11,24],[39,15,74],[44,31,96],[42,14,13],[18,5,17],[29,17,56],[39,32,91],[21,31,87],[14,34,25],[1,26,60],[42,48,38],[1,49,29],[33,42,1],[4,44,37],[24,47,45],[3,46,84],[39,40,95],[23,14,14],[7,37,66],[10,39,77],[23,48,10],[39,14,40],[30,10,81],[34,20,63],[24,23,85],[10,47,76],[15,41,26],[46,19,18],[31,39,33],[25,10,51],[13,6,77],[31,35,43],[20,2,3],[18,40,54],[24,45,46],[48,21,13],[36,30,29],[15,32,63],[12,6,91],[40,6,3],[1,13,93],[15,34,91],[30,36,84],[19,28,28],[35,1,27],[42,36,36],[33,12,17],[33,24,37],[26,9,41],[21,25,29],[31,48,6],[20,47,63],[44,5,67],[21,29,12],[11,23,35],[46,39,60],[48,50,20],[50,39,11],[12,45,34],[24,6,62],[14,26,35],[30,12,32],[44,47,1],[47,19,0],[50,25,23],[23,47,94],[4,9,78],[32,9,72],[23,35,26],[31,8,19],[44,43,17],[23,1,72],[33,30,53],[34,3,77],[18,31,9],[17,19,12],[38,28,17],[43,20,20],[5,9,72],[34,5,83],[1,36,54],[22,35,84],[44,12,57],[30,27,25],[36,14,44],[19,49,83],[7,45,42],[10,25,11],[27,48,54],[44,33,22],[10,7,46],[46,38,52],[40,30,61],[4,14,11],[15,6,54],[11,4,91],[11,38,70],[39,11,79],[10,32,69],[35,39,95],[41,32,90],[45,43,45],[36,1,69],[32,44,98],[28,31,36],[22,25,15],[1,42,65],[22,7,84],[13,42,43],[37,8,28],[8,32,96],[11,44,62],[13,33,84],[13,22,8],[42,41,91],[16,15,15],[48,1,80],[27,35,82],[49,15,45],[43,32,70],[38,7,50],[8,12,72],[25,47,37],[35,47,27],[43,47,97],[22,2,49],[36,31,26],[37,22,90],[1,15,8],[19,41,72],[28,46,45],[30,21,22],[46,4,76],[49,4,26],[41,46,97],[3,26,30],[21,24,33],[47,45,78],[39,24,93],[30,33,9],[4,11,83],[29,41,40],[6,14,65],[4,30,86],[34,14,47],[5,44,1],[13,1,64],[26,42,19],[14,43,34],[45,32,69],[30,2,31],[5,26,32],[34,24,70],[42,25,96],[46,14,70],[41,15,64],[21,30,10],[33,50,43],[3,6,54],[34,46,18],[50,2,95],[6,4,81],[5,47,25],[39,27,48],[22,5,74],[27,11,28],[32,42,3],[37,26,4],[49,19,11],[33,29,53],[41,30,65],[20,36,32],[2,38,59],[22,45,63],[30,37,58],[3,35,67],[49,24,77],[41,42,44],[50,36,32],[13,45,17],[32,3,43],[1,44,9],[11,2,47],[37,44,81],[13,23,15],[18,30,92],[16,27,38],[7,50,48],[2,41,18],[9,19,63],[13,32,1],[27,5,29],[50,8,27],[19,30,45],[5,23,89],[18,4,42],[1,35,36],[44,11,70],[14,21,60],[40,50,57],[45,47,65],[25,43,99],[34,47,88],[19,10,97],[27,20,61],[31,49,97],[5,43,96],[8,27,37],[41,3,20],[47,10,13],[28,30,22],[6,19,33],[9,45,59],[12,40,94],[16,12,40],[11,33,39],[29,1,82],[41,25,35],[44,35,24],[47,27,47],[8,48,35],[24,38,61],[10,6,91],[16,13,74],[39,37,87],[44,14,3],[42,7,55],[29,32,94],[41,43,50],[20,19,57],[19,36,54],[18,43,97],[29,7,94],[24,30,52],[7,20,62],[12,10,0],[9,4,78],[16,38,50],[40,23,28],[49,26,57],[11,40,61],[8,15,63],[38,8,64],[37,3,53],[37,24,3],[43,38,34],[40,45,22],[7,33,76],[50,13,33],[30,42,60],[39,35,68],[14,16,89],[26,13,19],[21,45,46],[37,46,26],[25,32,94],[36,45,3],[10,2,98],[19,24,51],[47,1,33],[41,40,31],[34,49,95],[42,10,0],[28,47,89],[34,6,71],[48,23,28],[43,4,78],[20,15,39],[9,11,6],[8,20,8],[17,45,88],[37,34,29],[12,44,89],[11,37,86],[14,44,61],[49,38,91],[20,1,96],[33,44,9],[42,13,78],[19,26,36],[33,6,67],[17,1,19],[25,28,14],[45,18,61],[47,36,91],[50,3,76],[26,45,95],[50,42,53],[49,47,29],[1,12,68],[28,36,44],[37,13,27],[49,1,23],[23,31,61],[7,14,81],[12,25,89],[5,50,75],[38,17,43],[39,25,99],[9,38,66],[16,3,41],[46,22,3],[18,37,57],[43,18,61],[41,10,0],[23,36,21],[1,48,14],[20,9,56],[23,6,94],[33,9,51],[44,41,75],[5,48,56],[16,17,91],[4,1,1],[12,36,15],[43,7,57],[5,6,35],[30,13,52],[11,39,85],[40,15,28],[45,48,0],[50,43,88],[27,39,1],[14,6,2],[10,43,89],[32,10,95],[47,43,11],[3,45,53],[9,46,67],[6,31,48],[25,38,80],[3,43,37],[11,48,54],[37,25,84],[36,21,12],[12,32,16],[49,14,90],[49,16,84],[4,46,28],[41,37,88],[26,20,67],[11,42,31],[10,33,39],[49,39,49],[43,10,73],[10,40,83],[26,46,89],[38,22,13],[29,13,80],[13,5,96],[34,22,78],[3,30,83],[47,49,51],[32,36,27],[7,39,49],[46,3,59],[37,17,38],[2,18,27],[50,1,84],[2,28,73],[3,9,46],[40,29,26],[16,41,33],[45,16,38],[6,29,14],[37,42,35],[18,25,25],[2,6,44],[47,23,34],[21,33,64],[32,13,11],[46,12,40],[49,21,74],[50,40,22],[12,1,54],[27,42,80],[6,9,3],[49,20,72],[11,14,31],[23,26,2],[11,22,10],[4,37,96],[19,3,66],[15,38,26],[3,2,81],[48,9,90],[34,10,27],[2,14,49],[31,14,37],[26,33,20],[7,43,96],[40,2,75],[36,26,72],[9,13,9],[36,47,88],[16,7,20],[14,8,90],[12,19,55],[25,34,92],[24,13,3],[34,39,99],[22,17,83],[45,31,87],[38,33,31],[23,22,99],[14,38,27],[29,22,42],[24,1,42],[3,14,21],[30,11,57],[39,17,31],[34,8,86],[37,6,70],[21,8,20],[35,30,42],[17,47,71],[45,50,75],[37,49,67],[2,42,7],[42,30,50],[26,49,50],[29,48,27],[27,24,68],[18,15,44],[6,25,26],[39,12,45],[30,3,50],[30,23,94],[4,41,94],[19,45,10],[47,25,97],[36,50,16],[50,18,57],[41,28,5],[1,9,73],[25,14,88],[32,14,46],[5,25,34],[48,46,47],[44,45,70],[45,41,40],[26,48,36],[21,7,37],[7,44,59],[38,29,61],[42,27,64],[47,26,77],[32,20,10],[19,9,34],[27,10,97],[2,25,51],[49,25,46],[21,20,48],[15,31,43],[34,36,66],[9,18,99],[29,20,14],[45,4,36],[31,15,39],[37,50,34],[16,10,49],[48,16,60],[39,7,42],[39,16,78],[44,36,88],[34,48,0],[4,35,90],[1,10,45],[45,10,4],[22,16,28],[31,42,36],[29,11,75],[1,33,64],[8,13,76],[16,32,16],[47,22,91],[17,48,83],[25,41,2],[26,11,67],[17,22,63],[27,26,57],[3,40,25],[47,6,25],[15,19,26],[15,23,36],[14,37,31],[6,40,67],[44,1,59],[47,24,1],[32,46,9],[36,40,76],[46,9,82],[45,23,90],[38,44,65],[11,24,79],[33,32,15],[20,50,46],[8,3,40],[40,46,30],[36,33,79],[47,50,0],[34,40,45],[3,42,39],[16,6,28],[25,6,37],[10,36,32],[15,36,60],[32,5,10],[36,7,81],[35,24,71],[1,8,31],[42,20,37],[12,18,16],[22,43,61],[44,39,46],[48,17,85],[26,25,75],[19,42,68],[32,18,44],[7,8,78],[29,27,69],[19,18,21],[43,50,42],[8,11,39],[37,32,59],[42,18,28],[39,28,10],[43,8,97],[7,11,90],[44,9,60],[35,43,53],[26,10,44],[11,36,26],[37,1,29],[37,27,51],[34,35,70],[29,5,8],[19,33,29],[13,3,32],[33,47,16],[7,12,74],[21,2,5],[38,37,35],[28,17,0],[37,16,47],[18,8,68],[28,26,22],[24,33,92],[38,1,39],[22,28,41],[20,32,4],[34,27,37],[27,34,58],[25,11,63],[21,28,94],[14,11,84],[43,30,99],[22,11,22],[10,3,52],[44,23,56],[15,26,72],[9,26,51],[13,49,8],[4,24,46],[20,43,97],[36,17,61],[6,32,37],[49,45,2],[49,29,30],[48,43,13],[21,37,40],[13,10,76],[47,20,10],[12,50,5],[44,6,19],[44,10,12],[15,46,18],[42,35,17],[33,35,89],[47,35,43],[12,22,74],[46,31,81],[36,15,3],[20,27,41],[31,45,95],[13,29,14],[32,28,36],[21,41,77],[40,44,35],[36,41,71],[1,39,85],[25,44,23],[6,38,31],[15,20,36],[33,22,20],[23,28,61],[20,3,24],[24,42,60],[31,46,46],[7,9,95],[29,4,93],[9,20,79],[22,24,39],[26,27,98],[35,32,25],[34,11,13],[40,32,43],[45,7,20],[40,7,2],[15,43,60],[19,43,63],[31,26,51],[37,2,87],[14,30,58],[27,31,6],[43,22,39],[50,35,73],[43,46,47],[32,47,33],[16,26,20],[11,10,35],[23,10,37],[22,36,40],[8,2,7],[41,12,51],[37,7,24],[17,5,1],[24,7,3],[35,10,14],[48,10,8],[47,14,62],[39,31,58],[11,7,79],[20,39,28],[44,24,8],[49,5,89],[35,49,10],[15,24,10],[38,15,63],[45,22,61],[16,34,42],[28,9,30],[47,8,65],[31,38,31],[50,46,71],[24,31,30],[34,19,3],[13,43,0],[28,2,93],[43,16,41],[44,27,69],[15,8,68],[4,15,15],[9,22,55],[17,38,44],[21,46,21],[48,49,35],[8,6,10],[48,32,8],[1,40,23],[17,31,94],[24,20,70],[21,22,26],[50,22,12],[47,48,13],[5,11,30],[43,40,39],[6,10,81],[9,15,8],[37,36,17],[11,29,67],[50,48,77],[25,4,91],[16,46,25],[30,32,54],[14,25,85],[32,48,41],[10,37,87],[37,4,50],[28,7,95],[13,27,19],[12,28,58],[42,22,23],[16,45,1],[29,42,42],[36,46,30],[10,13,94],[6,18,27],[34,42,8],[12,21,37],[24,26,71],[5,4,77],[14,20,20],[38,43,2],[23,37,59],[33,20,91],[22,3,21],[1,7,12],[22,8,42],[38,48,52],[42,8,25],[41,20,72],[23,38,54],[3,28,52],[25,33,80],[35,20,54],[48,25,3],[2,9,77],[9,48,47],[24,11,96],[1,20,67],[25,36,72],[17,46,81],[17,35,37],[46,40,99],[28,21,84],[21,15,74],[27,25,9],[14,19,52],[1,18,3],[21,11,26],[20,34,55],[30,46,80],[18,50,88],[33,43,77],[1,3,86],[17,14,57],[20,13,21],[21,4,75],[26,41,2],[5,49,87],[13,26,94],[32,43,13],[28,18,63],[2,7,47],[8,47,8],[44,26,55],[18,26,17],[40,17,6],[12,38,34],[2,13,62],[13,50,82],[2,30,47],[30,44,68],[28,43,21],[17,16,65],[45,17,0],[42,29,80],[48,41,50],[13,2,66],[29,44,39],[38,13,3],[43,24,93],[9,37,12],[26,37,12],[13,46,96],[32,7,27],[18,14,4],[8,25,19],[39,43,82],[3,11,31],[23,27,90],[10,45,56],[49,6,20],[20,5,0],[50,26,43],[4,25,9],[7,32,72],[15,47,48],[28,12,90],[31,16,32],[38,50,80],[45,11,78],[31,22,40],[5,15,22],[24,16,39],[11,41,75],[28,41,64],[33,34,99],[15,49,38],[35,38,46],[39,10,35],[6,11,69],[38,20,34],[40,38,34],[19,5,31],[13,40,54],[40,35,70],[35,15,50],[13,25,65],[7,19,51],[32,16,86],[23,18,14],[46,32,68],[33,1,31],[17,37,45],[27,30,34],[23,46,87],[12,15,81],[39,30,56],[41,48,31],[4,26,10],[50,21,16],[23,11,16],[40,22,61],[25,48,89],[13,21,60],[28,4,8],[43,39,39],[35,4,9],[15,30,28],[38,26,18],[6,1,54],[36,16,16],[43,41,28],[20,26,38],[34,12,80],[32,1,62],[25,3,71],[23,34,18],[42,6,50],[19,32,10],[35,5,74],[35,18,10],[41,49,79],[30,6,48],[50,11,24],[15,12,96],[38,11,86],[40,47,52],[4,7,81],[8,30,26],[27,4,4],[5,41,3],[21,19,54],[3,38,97],[49,48,11],[4,8,66],[26,18,44],[47,44,41],[8,14,58],[44,48,87],[45,8,44],[36,43,84],[27,19,15],[15,11,93],[26,23,94],[17,41,63],[42,24,21],[48,20,17],[9,44,13],[10,38,22],[47,34,86],[42,26,73],[2,20,68],[10,9,74],[20,21,8],[36,5,45],[24,8,99],[36,28,38],[50,24,4],[24,17,4],[39,19,69],[1,14,69],[20,35,81],[18,34,85],[8,19,74],[49,8,98],[34,21,26],[18,32,58],[8,36,47],[33,39,4],[14,49,6],[7,36,42],[2,32,63],[19,12,54],[32,37,67],[12,30,87],[3,18,21],[45,49,91],[8,41,4],[40,42,33],[8,5,98],[49,7,36],[21,12,35],[49,23,50],[12,48,92],[13,34,18],[5,16,60],[14,18,66],[7,28,98],[50,44,85],[49,36,53],[48,22,72],[50,32,62],[5,46,43],[49,41,33],[26,40,81],[7,29,47],[40,36,49],[6,15,0],[5,18,75],[39,44,92],[43,49,43],[11,5,65],[1,46,3],[24,14,68],[33,38,8],[28,44,20],[37,40,54],[33,21,58],[8,33,38]]");
        System.out.println(solution.networkDelayTime(times, 50, 22));
    }

    public static void main(String[] args) throws Exception {
        LC743 an = new LC743();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
